#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElementType;

typedef struct LNode
{
    ElementType data;
    struct LNode *next;
} LNode, *LinkList;

void PrintList(LinkList L)
{
    LNode *cur = L->next;
    while (cur)
    {
        printf("%3d", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 尾插建链表
void InitLinkList(LinkList &L, int len)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *tail = L, *node;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        node = (LNode *)malloc(sizeof(LNode));
        node->data = rand() % 100;
        node->next = tail->next;
        tail->next = node;
        tail = node;
    }
}

void ReverseList(LinkList L)
{
    LNode *head = L, *cur = L->next, *next;
    head->next = NULL;
    while (cur)
    {
        next = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = next;
    }
}

LNode *getMidList(LinkList L)
{
    LNode *fast, *slow;
    fast = slow = L;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

int main()
{
    LinkList L;
    InitLinkList(L, 15);
    PrintList(L);
    ReverseList(L);
    PrintList(L);
    LNode *node = getMidList(L);
    PrintList(node);
    return 0;
}